package com.leetcode.binarytree;

import com.leetcode.datastructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/10/27
 * @description: 100. 相同的树
 * 给定两个二叉树，编写一个函数来检验它们是否相同。
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 */
public class SameTree100A {

	/**
	 * 猜测两种遍历确定一棵二叉树。
	 * 答案：
	 * 前序遍历+中序遍历||中序遍历+后序遍历
	 * 通过输出的集合比较先序遍历和中序遍历。这个方法太愚笨了。
	 *
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSameTreeByOutput(TreeNode p, TreeNode q) {
		///1.临界条件判断
		if (p == null && q == null) {
			return true;
		}
		if (p == null || q == null) {
			return false;
		}

		///2.通过前序和中序确定数组
//		String pInOrder = "";
//		String qInOrder = "";
//		String pPreOrder = "";
//		String qPreOrder = "";
		List<Integer> pPreOrder = new ArrayList<>();
		List<Integer> qPreOrder = new ArrayList<>();
		List<Integer> pInOrder = new ArrayList<>();
		List<Integer> qInOrder = new ArrayList<>();

		preOrder(p, pPreOrder);
		preOrder(q, qPreOrder);
		inOrder(p, pInOrder);
		inOrder(q, qInOrder);

		///判断是否相等
		if (pPreOrder.size() == qPreOrder.size() && pInOrder.size() == qInOrder.size()) {
			for (int i = 0; i < pPreOrder.size(); i++) {
				if (!pPreOrder.get(i).equals(qPreOrder.get(i))) {
					return false;
				}

				if (!pInOrder.get(i).equals(qInOrder.get(i))) {
					return false;
				}
			}
			return true;
		}

		return false;
	}

	private void preOrder(TreeNode node, List<Integer> list) {
		if (node == null) {
			return;
		}
		list.add(node.val);
		if (node.left != null) {
			preOrder(node.left, list);
		}
		if (node.right != null) {
			preOrder(node.right, list);
		}
	}

	private void inOrder(TreeNode node, List<Integer> list) {
		if (node == null) {
			return;
		}
		if (node.left != null) {
			preOrder(node.left, list);
		}
		list.add(node.val);
		if (node.right != null) {
			preOrder(node.right, list);
		}
	}

	/**
	 * 事实证明确实不能用基本类型参数来试图改变其值
	 *
	 * @param str
	 */
	public void testChangeStr(String str) {
		str = str + str;
	}


	/**
	 * 直接通过指针进行比较（随便通过一种遍历方式，可以判断遍历方式）
	 *
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSameTreeWrong(TreeNode p, TreeNode q) {
		///1.临界条件判断
		if (p == null && q == null) {
			return true;
		}
		if (p == null || q == null) {
			return false;
		}
		if (p.val != q.val) {
			return false;
		}
		///2.通过先序遍历进行比较
		boolean isLeftSame = true;
		boolean isRightSame = true;
		///不能只判断一边
		if (p.left != null ) {
			isLeftSame = isSameTree(p.left, q.left);
		}
		if (!isLeftSame) {
			return false;
		}
		if (p.right != null) {
			isRightSame=isSameTree(p.right,p.right);
		}

		return isRightSame;
	}

	/**
	 * 直接通过指针比较（正确版）
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSameTree(TreeNode p, TreeNode q){
		if (p==null&&q==null){
			return true;
		}
		if (p==null||q==null){
			return false;
		}
		if (p.val!=q.val){
			return false;
		}
		return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
	}

	@Test
	public void testSameTree() {
		String s = "1";
		testChangeStr(s);
		System.out.println(s);

		TreeNode p = TreeNode.stringToTreeNode("[10,5,15]");
		TreeNode q = TreeNode.stringToTreeNode("[10,5,null,null,15]");
		System.out.println(isSameTree(p,q));
	}
}
